package org.example.l2;

import org.junit.jupiter.api.Test;

import java.util.*;

public class heap {

    public int findKthLargest(int[] nums,
                              int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.comparingInt(value -> -value));
        for (int num : nums) {
            queue.offer(num);
        }

        for (int i = 0; i < k - 1; i++) {
            queue.poll();
        }

        return queue.poll();
    }

    public int[] topKFrequent(int[] nums,
                              int k) {
        Map<Integer, Integer> map = new HashMap<>();
        Arrays.stream(nums).forEach(e -> map.put(e, map.getOrDefault(e, 0) + 1));
        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.comparingInt(map::get));
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (queue.size() < k) {
                queue.offer(entry.getKey());
                continue;
            }

            int v1 = entry.getValue(), min = map.get(queue.peek());
            if (v1 > min) {
                queue.poll();
                queue.offer(entry.getKey());
            }
        }

        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            res.add(queue.poll());
        }

        return res.stream().mapToInt(Integer::intValue).toArray();
    }

    @Test
    void aa() {
        int[] nums = new int[]{4, 1, -1, 2, -1, 2, 3};
        topKFrequent(nums, 2);
    }

}
